/*
 * Copyright (c) 2016, Mapbox
 *
 * Permission to use, copy, modify, and/or distribute this software for any purpose
 * with or without fee is hereby granted, provided that the above copyright notice
 * and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
 * THIS SOFTWARE.
 */

/**
 * @class EarCut
 */
Phaser.EarCut = {};

Phaser.EarCut.Triangulate = function (data, holeIndices, dim)
{
    dim = dim || 2;

    var hasHoles = holeIndices && holeIndices.length,
        outerLen = hasHoles ? holeIndices[0] * dim : data.length,
        outerNode = Phaser.EarCut.linkedList(data, 0, outerLen, dim, true),
        triangles = [];

    if (!outerNode) { return triangles; }

    var minX, minY, maxX, maxY, x, y, size;

    if (hasHoles) { outerNode = Phaser.EarCut.eliminateHoles(data, holeIndices, outerNode, dim); }

    // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
    if (data.length > 80 * dim)
    {
        minX = maxX = data[0];
        minY = maxY = data[1];

        for (var i = dim; i < outerLen; i += dim)
        {
            x = data[i];
            y = data[i + 1];
            if (x < minX) { minX = x; }
            if (y < minY) { minY = y; }
            if (x > maxX) { maxX = x; }
            if (y > maxY) { maxY = y; }
        }

        // minX, minY and size are later used to transform coords into integers for z-order calculation
        size = Math.max(maxX - minX, maxY - minY);
    }

    Phaser.EarCut.earcutLinked(outerNode, triangles, dim, minX, minY, size);

    return triangles;
};

// create a circular doubly linked list from polygon points in the specified winding order

Phaser.EarCut.linkedList = function (data, start, end, dim, clockwise)
{
    var sum = 0,
        i, j, last;

    // calculate original winding order of a polygon ring
    for (i = start, j = end - dim; i < end; i += dim)
    {
        sum += (data[j] - data[i]) * (data[i + 1] + data[j + 1]);
        j = i;
    }

    // link points into circular doubly-linked list in the specified winding order
    if (clockwise === (sum > 0))
    {
        for (i = start; i < end; i += dim) { last = Phaser.EarCut.insertNode(i, data[i], data[i + 1], last); }
    }
    else
    {
        for (i = end - dim; i >= start; i -= dim) { last = Phaser.EarCut.insertNode(i, data[i], data[i + 1], last); }
    }

    return last;
};

// eliminate colinear or duplicate points

Phaser.EarCut.filterPoints = function (start, end)
{
    if (!start) { return start; }
    if (!end) { end = start; }

    var p = start,
        again;
    do
    {
        again = false;

        if (!p.steiner && (Phaser.EarCut.equals(p, p.next) || Phaser.EarCut.area(p.prev, p, p.next) === 0))
        {
            Phaser.EarCut.removeNode(p);
            p = end = p.prev;
            if (p === p.next) { return null; }
            again = true;
        }
        else
        {
            p = p.next;
        }
    } while (again || p !== end);

    return end;
};

// main ear slicing loop which triangulates a polygon (given as a linked list)

Phaser.EarCut.earcutLinked = function (ear, triangles, dim, minX, minY, size, pass)
{
    if (!ear) { return; }

    // interlink polygon nodes in z-order
    if (!pass && size) { Phaser.EarCut.indexCurve(ear, minX, minY, size); }

    var stop = ear,
        prev, next;

    // iterate through ears, slicing them one by one
    while (ear.prev !== ear.next)
    {
        prev = ear.prev;
        next = ear.next;

        if (size ? Phaser.EarCut.isEarHashed(ear, minX, minY, size) : Phaser.EarCut.isEar(ear))
        {
            // cut off the triangle
            triangles.push(prev.i / dim);
            triangles.push(ear.i / dim);
            triangles.push(next.i / dim);

            Phaser.EarCut.removeNode(ear);

            // skipping the next vertice leads to less sliver triangles
            ear = next.next;
            stop = next.next;

            continue;
        }

        ear = next;

        // if we looped through the whole remaining polygon and can't find any more ears
        if (ear === stop)
        {
            // try filtering points and slicing again
            if (!pass)
            {
                Phaser.EarCut.earcutLinked(Phaser.EarCut.filterPoints(ear), triangles, dim, minX, minY, size, 1);

                // if this didn't work, try curing all small self-intersections locally
            }
            else if (pass === 1)
            {
                ear = Phaser.EarCut.cureLocalIntersections(ear, triangles, dim);
                Phaser.EarCut.earcutLinked(ear, triangles, dim, minX, minY, size, 2);

                // as a last resort, try splitting the remaining polygon into two
            }
            else if (pass === 2)
            {
                Phaser.EarCut.splitEarcut(ear, triangles, dim, minX, minY, size);
            }

            break;
        }
    }
};

// check whether a polygon node forms a valid ear with adjacent nodes

Phaser.EarCut.isEar = function (ear)
{
    var a = ear.prev,
        b = ear,
        c = ear.next;

    if (Phaser.EarCut.area(a, b, c) >= 0) { return false; } // reflex, can't be an ear

    // now make sure we don't have other points inside the potential ear
    var p = ear.next.next;

    while (p !== ear.prev)
    {
        if (Phaser.EarCut.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
            Phaser.EarCut.area(p.prev, p, p.next) >= 0) { return false; }
        p = p.next;
    }

    return true;
};

Phaser.EarCut.isEarHashed = function (ear, minX, minY, size)
{
    var a = ear.prev,
        b = ear,
        c = ear.next;

    if (Phaser.EarCut.area(a, b, c) >= 0) { return false; } // reflex, can't be an ear

    // triangle bbox; min & max are calculated like this for speed
    var minTX = a.x < b.x ? (a.x < c.x ? a.x : c.x) : (b.x < c.x ? b.x : c.x),
        minTY = a.y < b.y ? (a.y < c.y ? a.y : c.y) : (b.y < c.y ? b.y : c.y),
        maxTX = a.x > b.x ? (a.x > c.x ? a.x : c.x) : (b.x > c.x ? b.x : c.x),
        maxTY = a.y > b.y ? (a.y > c.y ? a.y : c.y) : (b.y > c.y ? b.y : c.y);

    // z-order range for the current triangle bbox;
    var minZ = Phaser.EarCut.zOrder(minTX, minTY, minX, minY, size),
        maxZ = Phaser.EarCut.zOrder(maxTX, maxTY, minX, minY, size);

    // first look for points inside the triangle in increasing z-order
    var p = ear.nextZ;

    while (p && p.z <= maxZ)
    {
        if (p !== ear.prev && p !== ear.next &&
            Phaser.EarCut.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
            Phaser.EarCut.area(p.prev, p, p.next) >= 0) { return false; }
        p = p.nextZ;
    }

    // then look for points in decreasing z-order
    p = ear.prevZ;

    while (p && p.z >= minZ)
    {
        if (p !== ear.prev && p !== ear.next &&
            Phaser.EarCut.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
            Phaser.EarCut.area(p.prev, p, p.next) >= 0) { return false; }
        p = p.prevZ;
    }

    return true;
};

// go through all polygon nodes and cure small local self-intersections

Phaser.EarCut.cureLocalIntersections = function (start, triangles, dim)
{
    var p = start;
    do
    {
        var a = p.prev,
            b = p.next.next;

        // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
        if (Phaser.EarCut.intersects(a, p, p.next, b) && Phaser.EarCut.locallyInside(a, b) && Phaser.EarCut.locallyInside(b, a))
        {
            triangles.push(a.i / dim);
            triangles.push(p.i / dim);
            triangles.push(b.i / dim);

            // remove two nodes involved
            Phaser.EarCut.removeNode(p);
            Phaser.EarCut.removeNode(p.next);

            p = start = b;
        }
        p = p.next;
    } while (p !== start);

    return p;
};

// try splitting polygon into two and triangulate them independently

Phaser.EarCut.splitEarcut = function (start, triangles, dim, minX, minY, size)
{
    // look for a valid diagonal that divides the polygon into two
    var a = start;
    do
    {
        var b = a.next.next;
        while (b !== a.prev)
        {
            if (a.i !== b.i && Phaser.EarCut.isValidDiagonal(a, b))
            {
                // split the polygon in two by the diagonal
                var c = Phaser.EarCut.splitPolygon(a, b);

                // filter colinear points around the cuts
                a = Phaser.EarCut.filterPoints(a, a.next);
                c = Phaser.EarCut.filterPoints(c, c.next);

                // run earcut on each half
                Phaser.EarCut.earcutLinked(a, triangles, dim, minX, minY, size);
                Phaser.EarCut.earcutLinked(c, triangles, dim, minX, minY, size);
                return;
            }
            b = b.next;
        }
        a = a.next;
    } while (a !== start);
};

// link every hole into the outer loop, producing a single-ring polygon without holes

Phaser.EarCut.eliminateHoles = function (data, holeIndices, outerNode, dim)
{
    var queue = [],
        i, len, start, end, list;

    for (i = 0, len = holeIndices.length; i < len; i++)
    {
        start = holeIndices[i] * dim;
        end = i < len - 1 ? holeIndices[i + 1] * dim : data.length;
        list = Phaser.EarCut.linkedList(data, start, end, dim, false);
        if (list === list.next) { list.steiner = true; }
        queue.push(Phaser.EarCut.getLeftmost(list));
    }

    queue.sort(Phaser.EarCut.compareX);

    // process holes from left to right
    for (i = 0; i < queue.length; i++)
    {
        Phaser.EarCut.eliminateHole(queue[i], outerNode);
        outerNode = Phaser.EarCut.filterPoints(outerNode, outerNode.next);
    }

    return outerNode;
};

Phaser.EarCut.compareX = function (a, b)
{
    return a.x - b.x;
};

// find a bridge between vertices that connects hole with an outer ring and and link it

Phaser.EarCut.eliminateHole = function (hole, outerNode)
{
    outerNode = Phaser.EarCut.findHoleBridge(hole, outerNode);
    if (outerNode)
    {
        var b = Phaser.EarCut.splitPolygon(outerNode, hole);
        Phaser.EarCut.filterPoints(b, b.next);
    }
};

// David Eberly's algorithm for finding a bridge between hole and outer polygon

Phaser.EarCut.findHoleBridge = function (hole, outerNode)
{
    var p = outerNode,
        hx = hole.x,
        hy = hole.y,
        qx = -Infinity,
        m;

    /*
     * find a segment intersected by a ray from the hole's leftmost point to the left;
     * segment's endpoint with lesser x will be potential connection point
     */
    do
    {
        if (hy <= p.y && hy >= p.next.y)
        {
            var x = p.x + (hy - p.y) * (p.next.x - p.x) / (p.next.y - p.y);
            if (x <= hx && x > qx)
            {
                qx = x;
                m = p.x < p.next.x ? p : p.next;
            }
        }
        p = p.next;
    } while (p !== outerNode);

    if (!m) { return null; }

    if (hole.x === m.x) { return m.prev; } // hole touches outer segment; pick lower endpoint

    /*
     * look for points inside the triangle of hole point, segment intersection and endpoint;
     * if there are no points found, we have a valid connection;
     * otherwise choose the point of the minimum angle with the ray as connection point
     */

    var stop = m,
        tanMin = Infinity,
        tan;

    p = m.next;

    while (p !== stop)
    {
        if (hx >= p.x && p.x >= m.x &&
            Phaser.EarCut.pointInTriangle(hy < m.y ? hx : qx, hy, m.x, m.y, hy < m.y ? qx : hx, hy, p.x, p.y))
        {
            tan = Math.abs(hy - p.y) / (hx - p.x); // tangential

            if ((tan < tanMin || (tan === tanMin && p.x > m.x)) && Phaser.EarCut.locallyInside(p, hole))
            {
                m = p;
                tanMin = tan;
            }
        }

        p = p.next;
    }

    return m;
};

// interlink polygon nodes in z-order

Phaser.EarCut.indexCurve = function (start, minX, minY, size)
{
    var p = start;
    do
    {
        if (p.z === null) { p.z = Phaser.EarCut.zOrder(p.x, p.y, minX, minY, size); }
        p.prevZ = p.prev;
        p.nextZ = p.next;
        p = p.next;
    } while (p !== start);

    p.prevZ.nextZ = null;
    p.prevZ = null;

    Phaser.EarCut.sortLinked(p);
};

/*
 * Simon Tatham's linked list merge sort algorithm
 * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
 */

Phaser.EarCut.sortLinked = function (list)
{
    var i, p, q, e, tail, numMerges, pSize, qSize,
        inSize = 1;

    do
    {
        p = list;
        list = null;
        tail = null;
        numMerges = 0;

        while (p)
        {
            numMerges++;
            q = p;
            pSize = 0;
            for (i = 0; i < inSize; i++)
            {
                pSize++;
                q = q.nextZ;
                if (!q) { break; }
            }

            qSize = inSize;

            while (pSize > 0 || (qSize > 0 && q))
            {
                if (pSize === 0)
                {
                    e = q;
                    q = q.nextZ;
                    qSize--;
                }
                else if (qSize === 0 || !q)
                {
                    e = p;
                    p = p.nextZ;
                    pSize--;
                }
                else if (p.z <= q.z)
                {
                    e = p;
                    p = p.nextZ;
                    pSize--;
                }
                else
                {
                    e = q;
                    q = q.nextZ;
                    qSize--;
                }

                if (tail) { tail.nextZ = e; }
                else { list = e; }

                e.prevZ = tail;
                tail = e;
            }

            p = q;
        }

        tail.nextZ = null;
        inSize *= 2;
    } while (numMerges > 1);

    return list;
};

// z-order of a point given coords and size of the data bounding box

Phaser.EarCut.zOrder = function (x, y, minX, minY, size)
{
    // coords are transformed into non-negative 15-bit integer range
    x = 32767 * (x - minX) / size;
    y = 32767 * (y - minY) / size;

    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;

    y = (y | (y << 8)) & 0x00FF00FF;
    y = (y | (y << 4)) & 0x0F0F0F0F;
    y = (y | (y << 2)) & 0x33333333;
    y = (y | (y << 1)) & 0x55555555;

    return x | (y << 1);
};

// find the leftmost node of a polygon ring

Phaser.EarCut.getLeftmost = function (start)
{
    var p = start,
        leftmost = start;
    do
    {
        if (p.x < leftmost.x) { leftmost = p; }
        p = p.next;
    } while (p !== start);

    return leftmost;
};

// check if a point lies within a convex triangle

Phaser.EarCut.pointInTriangle = function (ax, ay, bx, by, cx, cy, px, py)
{
    return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
        (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
        (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
};

// check if a diagonal between two polygon nodes is valid (lies in polygon interior)

Phaser.EarCut.isValidDiagonal = function (a, b)
{
    return Phaser.EarCut.equals(a, b) || a.next.i !== b.i && a.prev.i !== b.i && !Phaser.EarCut.intersectsPolygon(a, b) &&
        Phaser.EarCut.locallyInside(a, b) && Phaser.EarCut.locallyInside(b, a) && Phaser.EarCut.middleInside(a, b);
};

// signed area of a triangle

Phaser.EarCut.area = function (p, q, r)
{
    return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
};

// check if two points are equal

Phaser.EarCut.equals = function (p1, p2)
{
    return p1.x === p2.x && p1.y === p2.y;
};

// check if two segments intersect

Phaser.EarCut.intersects = function (p1, q1, p2, q2)
{
    return Phaser.EarCut.area(p1, q1, p2) > 0 !== Phaser.EarCut.area(p1, q1, q2) > 0 &&
        Phaser.EarCut.area(p2, q2, p1) > 0 !== Phaser.EarCut.area(p2, q2, q1) > 0;
};

// check if a polygon diagonal intersects any polygon segments

Phaser.EarCut.intersectsPolygon = function (a, b)
{
    var p = a;
    do
    {
        if (p.i !== a.i && p.next.i !== a.i && p.i !== b.i && p.next.i !== b.i &&
            Phaser.EarCut.intersects(p, p.next, a, b)) { return true; }
        p = p.next;
    } while (p !== a);

    return false;
};

// check if a polygon diagonal is locally inside the polygon

Phaser.EarCut.locallyInside = function (a, b)
{
    return Phaser.EarCut.area(a.prev, a, a.next) < 0 ?
        Phaser.EarCut.area(a, b, a.next) >= 0 && Phaser.EarCut.area(a, a.prev, b) >= 0 :
        Phaser.EarCut.area(a, b, a.prev) < 0 || Phaser.EarCut.area(a, a.next, b) < 0;
};

// check if the middle point of a polygon diagonal is inside the polygon

Phaser.EarCut.middleInside = function (a, b)
{
    var p = a,
        inside = false,
        px = (a.x + b.x) / 2,
        py = (a.y + b.y) / 2;
    do
    {
        if (((p.y > py) !== (p.next.y > py)) && (px < (p.next.x - p.x) * (py - p.y) / (p.next.y - p.y) + p.x))
        { inside = !inside; }
        p = p.next;
    } while (p !== a);

    return inside;
};

/*
 * link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two;
 * if one belongs to the outer ring and another to a hole, it merges it into a single ring
 */

Phaser.EarCut.splitPolygon = function (a, b)
{
    var a2 = new Phaser.EarCut.Node(a.i, a.x, a.y),
        b2 = new Phaser.EarCut.Node(b.i, b.x, b.y),
        an = a.next,
        bp = b.prev;

    a.next = b;
    b.prev = a;

    a2.next = an;
    an.prev = a2;

    b2.next = a2;
    a2.prev = b2;

    bp.next = b2;
    b2.prev = bp;

    return b2;
};

// create a node and optionally link it with previous one (in a circular doubly linked list)

Phaser.EarCut.insertNode = function (i, x, y, last)
{
    var p = new Phaser.EarCut.Node(i, x, y);

    if (!last)
    {
        p.prev = p;
        p.next = p;
    }
    else
    {
        p.next = last.next;
        p.prev = last;
        last.next.prev = p;
        last.next = p;
    }
    return p;
};

Phaser.EarCut.removeNode = function (p)
{
    p.next.prev = p.prev;
    p.prev.next = p.next;

    if (p.prevZ) { p.prevZ.nextZ = p.nextZ; }
    if (p.nextZ) { p.nextZ.prevZ = p.prevZ; }
};

Phaser.EarCut.Node = function (i, x, y)
{
    // vertice index in coordinates array
    this.i = i;

    // vertex coordinates
    this.x = x;
    this.y = y;

    // previous and next vertice nodes in a polygon ring
    this.prev = null;
    this.next = null;

    // z-order curve value
    this.z = null;

    // previous and next nodes in z-order
    this.prevZ = null;
    this.nextZ = null;

    // indicates whether this is a steiner point
    this.steiner = false;
};

